/*
 * Суффиксный массив
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <limits.h>

struct suf_array {
	int sa;
	int k1, k2;
};

/* {{{ memory allocation wrappers */
extern char *
s_calloc(size_t n, size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): calloc %lu times %lu bytes (tot %.4f MiB)\n",
			__func__, n, size, ((float) n * size) / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = calloc(n, size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return (char *) ptr;
}

extern char *
s_malloc(size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): malloc %lu bytes (%.4f MiB)\n",
			__func__, size, (float) size / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = malloc(size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return (char *) ptr;
}

extern char *
s_realloc(char *oldptr, size_t newsize)
{
	void *newptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): realloc oldptr %p for new size of %lu (%.4f MiB)\n",
			__func__, oldptr, newsize, (float) newsize / (1024.0f * 1024.0f));
#endif
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): newptr %p\n", __func__, newptr);
#endif /* MEMDEBUG */
	return (char *) newptr;
}

void
s_free(void *ptr)
{
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): freeing %p\n", __func__, ptr);
#endif
	free(ptr);
}
/* }}} */

int
cmp_sa(const void *p1, const void *p2)
{
	const struct suf_array *s1 = (struct suf_array *) p1, *s2 = (struct suf_array *) p2;

	assert(s1 != NULL);
	assert(s2 != NULL);

	if (s1->k1 < s2->k1)
		return -1;
	else if (s1->k1 > s2->k1)
		return 1;
	else if (s1->k2 < s2->k2)
		return -1;
	else if (s1->k2 > s2->k2)
		return 1;

	return 0;
}

struct suf_array *
sufarray__build(const char *string, const int n)
{
	struct suf_array *A;
	int i, h = 1;
	int *isa, rank = 0;

	A = (struct suf_array *) s_calloc(n, sizeof *A);
	isa = (int *) s_calloc(n, sizeof *isa);

	for (i = 0; i < n; i++) {
		A[i].sa = i;
		A[i].k1 = 0;
		A[i].k2 = string[i];
	}

	while (rank != n - 1) {
		qsort(A, n, sizeof A[0], &cmp_sa);

		isa[0] = rank = 0;
		for (i = 1; i < n; i++) {
			if (cmp_sa(A + i - 1, A + i))
				rank++;
			isa[A[i].sa] = rank;
		}

		if (rank == n - 1)
			break; /* XXX */

		for (i = 0; i < n; i++) {
			A[i].k1 = isa[A[i].sa];
			if (A[i].sa + h >= n)
				A[i].k2 = -1;
			else
				A[i].k2 = isa[A[i].sa + h];
		}

		h *= 2;
	}

	free(isa);
	return A;
}

int
main(int argc, char **argv)
{
	char *string;
	struct suf_array *A;
	int i, n;

	string = s_malloc(50002UL);
	scanf("%s", string);
	A = sufarray__build(string, n = strlen(string));

	for (i = 0; i < n; i++)
		printf("%d%c", A[i].sa + 1, (i == n - 1) ? '\n' : ' ');

	free(string);
	free(A);
	return 0;
}
